10867. Максимум
в унимодальной последовательности
Последовательность ai
называется унимодальной если существует такой индекс p что a1
< a2 < ... < ap и ap
> ap+1 > ... > an.
Значение ap является наибольшим в этой последовательности.
Найдите это значение.
Вход. Первая строка содержит размер
массива n (n ≤ 106). Следующая строка содержит n
натуральных чисел, представляющих унимодальную последовательность. Числа в
массиве не превышают 109.
Выход. Выведите наибольший элемент в
унимодальной последовательности.
|
Пример
входа 1 |
Пример
выхода 1 |
|
10 2 4 7 12 18 19 16
11 8 3 |
19 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
6 3 5 7 11 15 17 |
17 |
РЕШЕНИЕ
тернарный
поиск
Анализ алгоритма
Максимум в унимодальной последовательности ищем при помощи
тернарного поиска. Разделим текущий интервал поиска [left; right] точками a и b на три равные части:
·
a = left + (right – left)
/ 3;
·
b = left + 2 * (right – left)
/ 3;
При поиске максимума если:
·
m[a] < m[b], то поиск продолжаем на отрезке [a; right];
·
m[a] ≥ m[b], то поиск продолжаем на отрезке [left; b];
Пример
Рассмотрим первый тест. Проведем первую итерацию тернарного
поиска.
Отрезок [left;
right] = [0; 9] разбивается точками a
= 3 и b = 6 на три равные части. Поскольку m[a] <
m[b], то
поиск продолжаем на отрезке [a;
right] = [3; 9].
Реализация алгоритма
Входную последовательность храним в массиве m.
#define MAX 1000001
int m[MAX];
Функция ternary_search возвращает наибольший элемент в унимодальной
последовательности m[left;
right].
int ternary_search(int left, int right)
{
Если
последовательность содержит не более трех элементов, то максимум среди них ищем
обычным перебором.
if (right - left < 3)
{
int res = m[left++];
while (left <= right)
res = max(res, m[left++]);
return res;
}
Отрезок
[left; right] точками a и b делим на три равные части.
int a = left + (right - left) / 3;
int b = left + 2 * (right - left) / 3;
Сравниваем
m[a] и m[b]. В зависимости от результата
продолжаем поиск или на отрезке [a;
right], или
на отрезке [left; b].
if (m[a] < m[b]) return ternary_search(a, right);
return ternary_search(left, b);
}
Основная
часть программы. Читаем входной массив.
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &m[i]);
Запускаем
тернарный поиск и выводим наибольший элемент в унимодальной последовательности.
printf("%d\n", ternary_search(0, n - 1));